1150. K-ое число (Easy)

Вы работаете на компанию МакроХард в отделе структуры данных. После неудачного решения предыдущей задаче о вставки ключей, Вас попросили написать новую структуру данных, позволяющую быстро находить k-ую порядковую статистику на указанном отрезке.

Задан массив a[1...n] различных целых чисел. Необходимо отвечать на вопросы Q(i, j, k) следующего вида: "Найти k-ое число на отрезке a[i...j], если все числа на этом отрезке предварительно отсортировать".

Например, рассмотрим отрезок a = (1, 5, 2, 6, 3, 7, 4). Рассмотрим запрос Q(2, 5, 3). Отрезком a[2...5] будет (5, 2, 6, 3). Отсортировав числа, получим (2, 3, 5, 6). Третьим элементом будет 5. Ответом на запрос будет 5.

Вход. Первая строка содержит размер массива n и количество запросов m (1 ≤ n, m ≤ 100).

Вторая строка содержит n разных целых чисел, не превосходящих 10⁹ по абсолютному значению – массив чисел, к которому будут ставиться запросы.

Следующие m строк содержат запросы, каждый из которых состоит из трех чисел: i, j и k (0 ≤ i ≤ j ≤ n, 0 ≤ k ≤ j – i + 1) и представляет собой запрос Q(i, j, k).

Выход. Для каждого запроса вывести k-ое число в отсортированном отрезке a[i...j].

Пример входа	Пример выхода
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3	5 6 3

РЕШЕНИЕ

моделирование

Анализ алгоритма

В варианте EASY достаточно промоделировать требуемое при помощи обыкновенного массива. То есть при выполнении запроса Q(i, j, k) скопируем часть массива a[i...j] в temp[0..j – i + 1], отсортируем содержимое temp и вернем его (k – 1)-ый элемент (индексы в запросах начинаются с единицы).

Пример

Рассмотрим выполнение первого запроса.

Реализация алгоритма

Объявим входной массив a и вспомогательный temp.

#define MAX 110

int a[MAX], temp[MAX];

Читаем входной массив а.

scanf("%d %d",&n,&m);

for(i = 0; i < n; i++) scanf("%d",&a[i]);

Обрабатываем q запросов.

for(q = 0; q < m; q++)

{

scanf("%d %d %d",&i,&j,&k);

len = j - i + 1;

Копируем a[i...j] в temp[0..j – i + 1] (всего (j – i + 1) * sizeof(int) байт), сортируем элементы массива temp.

memcpy(temp,a+i-1,len*sizeof(int));

sort(temp,temp+len);

Выводим (k – 1)-ый элемент массива temp в качестве ответа.

printf("%d\n",temp[k-1]);

}